package dynamicProgramming;

public class Bag01 {


    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        int goods = weight.length;
//        即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
        int[][] dp=new int[goods][bagSize+1];
        for (int i = weight[0]; i <=bagSize ; i++) {
            dp[0][i]=value[0];
        }
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <=bagSize ; j++) {
                if (j<weight[i]){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }
    }


    public static void testWeightBagProblem1(int[] weight, int[] value, int bagSize){
        int goods = weight.length;
        int[] dp=new int[bagSize+1];
         dp[0]=0;
//  CKG TODO 2023/5/12: 先遍历物品
        for (int i = 1; i < goods; i++) {
            //  CKG TODO 2023/5/12: 再遍历背包
            for (int j = bagSize; j >=weight[i] ; j--) {
                dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]);
            }
        }
    }

}
